package list;

/**题目：有序链表去除重复的节点
 * @Author Gavin
 * @date 2022.01.09 14:38
 */
public class list_10 {
    /**
     * 第一种方法：
     * 采用两个指针进行不断的移动
     */
    public ListNode solution(ListNode head){
        if(head==null||head.next==null)return head;
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode prev=dummy,cur=prev.next;
        while (cur!=null){
            while (cur.next!=null&&cur.val==cur.next.val)cur=cur.next;
            //上面循环完毕之后cur肯定是移动到重复元素的最后一个
            if(prev.next!=cur)prev.next=cur.next;
            else prev=prev.next;
            cur=cur.next;
        }
        return dummy.next;
    }
    /**
     * 第二种方法：递归的方法
     */
    public ListNode solution_2(ListNode head){
        if(head==null||head.next==null)return head;
        if(head.val==head.next.val){
            ListNode pNode=head.next;
            while (pNode!=null&&pNode.val==head.val){
                pNode=pNode.next;
            }
            return solution_2(pNode);
        }else{
            head.next=solution_2(head.next);
            return head;
        }
    }
}
